#include <list>
#include <unordered_map>
#include <iostream>
#include <string>

template <typename Key, typename Val>
class LRUCache
{
    using ListIt = typename std::list<std::pair<Key, Val>>::iterator;

    std::list<std::pair<Key, Val>> _LRUlist;
    size_t _capacity;
    std::unordered_map<Key, ListIt> _hashmap;

public:
    LRUCache(size_t capacity) : _capacity(capacity) {}

    Val get(const Key &key)
    {
        auto it = _hashmap.find(key);
        if (it != _hashmap.end())
        {
            // Move the key to the front of the LRU list
            ListIt listit = it->second;
            _LRUlist.splice(_LRUlist.begin(), _LRUlist, listit);
            return listit->second;
        }
        else
        {
            // Return default value if key not found (or throw/assert as needed)
            return Val{};
        }
    }

    void put(const Key &key, const Val &value)
    {
        auto it = _hashmap.find(key);
        if (it == _hashmap.end())
        {
            // Evict the least recently used item if cache is full
            if (_hashmap.size() == _capacity)
            {
                auto back = _LRUlist.back();
                _hashmap.erase(back.first);
                _LRUlist.pop_back();
            }
            // Insert new key-value pair at the front
            _LRUlist.emplace_front(key, value);
            _hashmap.emplace(key, _LRUlist.begin());
        }
        else
        {
            // Update existing value and move to front
            ListIt listit = it->second;
            listit->second = value;
            _LRUlist.splice(_LRUlist.begin(), _LRUlist, listit);
        }
    }
};

int main()
{
    // 测试1: 键为int，值为string
    LRUCache<int, std::string> cache(3);

    std::cout << "--- Test int/string LRU Cache (Capacity=3) ---\n";
    cache.put(1, "Apple");
    cache.put(2, "Banana");
    cache.put(3, "Cherry");

    std::cout << "Get 2: " << cache.get(2) << "\n"; // Banana (访问后，2成为最新)
    cache.put(4, "Durian");                         // 淘汰1 (Apple)
    std::cout << "Get 1: " << cache.get(1) << "\n"; // 空 (已淘汰)
    std::cout << "Get 3: " << cache.get(3) << "\n"; // Cherry
    cache.put(3, "Coconut");                        // 更新3的值
    std::cout << "Get 3: " << cache.get(3) << "\n"; // Coconut

    // 测试2: 键为string，值为double
    LRUCache<std::string, double> stockCache(2);
    std::cout << "\n--- Test string/double LRU Cache (Capacity=2) ---\n";
    stockCache.put("AAPL", 182.5);
    stockCache.put("GOOG", 142.3);
    std::cout << "Get AAPL: " << stockCache.get("AAPL") << "\n"; // 182.5
    stockCache.put("MSFT", 410.2);                               // 淘汰GOOG
    std::cout << "Get GOOG: " << stockCache.get("GOOG") << "\n"; // 0 (默认double值)
    std::cout << "Get MSFT: " << stockCache.get("MSFT") << "\n"; // 410.2

    return 0;
}